//--------------------------------------------------------------------
//
//  Laboratory 8                                           listlnk2.cpp
//
//  Class implementation of the List ADT
//
//--------------------------------------------------------------------

#ifndef LISTLNK2_CPP
#define LISTLNK2_CPP

#include <new>
#include <stdexcept>
#include <iostream>
#include "listlnk2.h"

using namespace std;

// Constructor of the class ListNode
template < class DT, class KF >
ListNode<DT,KF>::ListNode ( const DT &nodeData, ListNode<DT,KF> *nextPtr )
  :dataItem(nodeData),next(nextPtr){};

//--------------------------------------------------------------------
// Constructor
template < class DT, class KF >
List<DT,KF>::List ( int ignored ):head(NULL),cursor(NULL){};

// Copy constructor
template < class DT, class KF >
List<DT,KF>::List ( const List<DT,KF> &srcList )
{
    ListNode<DT,KF> *p = srcList.head;
    ListNode<DT,KF> *holdCursor;
    if (srcList.head == NULL)    // Check if srcList is empty
        head = cursor = NULL;
    else
    {
        head = cursor = NULL;
        while(p!=NULL)
        {
            insert(p->dataItem);
            if (p == srcList.cursor)
                holdCursor = cursor;
            p = p->next;
        }
        this->cursor = holdCursor;
    }
}

// Destructor
template < class DT, class KF >
List<DT,KF>::~List ()
{
    clear();
}

// Overloaded assignment operator
template < class DT, class KF >
const List<DT,KF> &List<DT,KF>::operator= ( const List<DT,KF> &srcList )
{
    ListNode<DT,KF> *p = srcList.head;
    ListNode<DT,KF> *holdCursor;
    if (this==&srcList)
        return *this;
    else
    {
        clear();
        while(p!=NULL)
        {
            insert(p->dataItem);
            if (p == srcList.cursor)
                holdCursor = cursor;
            p = p->next;
        }
        this->cursor = holdCursor;
    }
}

// List manipulation operations
template < class DT, class KF >
void List<DT,KF>::insert ( const DT &newData )        // Insert after cursor
        throw ( bad_alloc )
{
    ListNode<DT,KF> *p;
    if (isFull()){
        throw bad_alloc();
    }else if (isEmpty()){
        p = new ListNode<DT,KF>(newData,NULL);
        head = cursor = p;
    }else{
        p = new ListNode<DT,KF>(newData,cursor->next);
        cursor->next = p;
        cursor = p;
    }
}

template < class DT, class KF >
void List<DT,KF>::remove () throw ( logic_error )      // Remove data item
{
    ListNode<DT,KF> *p, *toDel;
    if (isEmpty())
        throw logic_error("List is empty! Cannot remove!");
    else if(head==cursor){
        toDel = head;
        head = cursor = head->next;
    } else {
        toDel = cursor;
        for(p=head; p->next!=cursor; p=p->next);
        p->next = cursor = toDel->next;
        if (cursor==NULL)
            cursor = head;
    }
    delete toDel;
}

template < class DT, class KF >
void List<DT,KF>::replace ( const DT &newData )       // Replace data item
        throw ( logic_error )
{
    ListNode<DT,KF> *p, *q, *toDel;
    if (isEmpty())
        throw logic_error("List is empty! Cannot replace!");
    else if(head==cursor){
        toDel = head;
        p = new ListNode<DT,KF>(newData,head->next);
        head = cursor = p;
    } else {
        toDel = cursor;
        p = new ListNode<DT,KF>(newData,cursor->next);
        for(q=head; q->next!=cursor; q=q->next);
        q->next = cursor = p;
    }
    delete toDel;
}

template < class DT, class KF >
void List<DT,KF>::clear ()                           // Clear list
{
    ListNode<DT,KF>* toDel;
    while(head != NULL)
    {
        toDel = head;
        head = head->next;
        delete toDel;
    }
    cursor = NULL;
}

// List status operations
template < class DT, class KF >
bool List<DT,KF>::isEmpty () const                   // List is empty
{
    if (head==NULL)
        return true;
    else
        return false;
}

template < class DT, class KF >
bool List<DT,KF>::isFull () const                    // List is full
{
    ListNode<DT,KF>* location;
    try
    {
        DT temp;
        location = new ListNode<DT,KF>(temp,NULL);
        delete location;
        return false;
    } catch(std::bad_alloc exception){
        return true;
    }
}

// List iteration operations
template < class DT, class KF >
void List<DT,KF>::gotoBeginning ()                    // Go to beginning
        throw ( logic_error )
{
    if (isEmpty())
        throw logic_error("List is empty! Cannot gotoBeginning!");
    else
        cursor = head;
}


template < class DT, class KF >
void List<DT,KF>::gotoEnd ()                          // Go to end
        throw ( logic_error )
{
    if (isEmpty())
        throw logic_error("List is empty! Cannot gotoEnd!");
    else{
        while(cursor->next!=NULL)
            cursor = cursor->next;
    }
}

template < class DT, class KF >
bool List<DT,KF>::gotoNext ()                         // Go to next data item
        throw ( logic_error )
{
    if (isEmpty())
        throw logic_error("List is empty! Cannot gotoNext!");
    else if(cursor->next==NULL)
        return false;
    else{
        cursor = cursor->next;
        return true;
    }
}

template < class DT, class KF >
bool List<DT,KF>::gotoPrior ()                        // Go to prior item
        throw ( logic_error )
{
    ListNode<DT,KF>* p;
    if (isEmpty())
        throw logic_error("List is empty! Cannot gotoPrior!");
    else if (cursor==head)
        return false;
    else{
        for(p=head; p->next!=cursor; p=p->next);
        cursor = p;
        return true;
    }
}

template < class DT, class KF >
DT List<DT,KF>::getCursor () const                    // Return item
        throw ( logic_error )
{
    if (isEmpty())
        throw logic_error("List is empty!");
    else {
        DT retData = cursor->dataItem;
        return retData;
    }
}

// Output the list structure -- used in testing/debugging
template < class DT, class KF >
void List<DT,KF>::showStructure () const

// Outputs the items in a list. If the list is empty, outputs
// "Empty list". This operation is intended for testing and
// debugging purposes only.

{
    ListNode<DT,KF> *p;   // Iterates through the list

    if ( head == 0 )
       cout << "Nothing" << endl;
    else
    {
       for ( p = head ; p != 0 ; p = p->next )
           if ( p == cursor )
              cout << "[" << p->dataItem.getKey() << "] \n";
           else
              cout << p->dataItem.getKey() << " \n";
       cout << endl;
    }
}


// Linear search function, return found/not fount, and 
//  fill the DT container with certain item if found
template < class DT, class KF >
bool List<DT,KF>::search(KF searchKey, DT &searchData)
{
    bool result = false;         // Result to return
    ListNode<DT,KF> *p = head;   // Iterates through the list
    // Search from the head to the end
    while(p!=NULL)
    {
        if ( p->dataItem.getKey() == searchKey )
        {
            searchData = p->dataItem;
            cursor = p;
            result = true;
            break;
        } else {
            p = p->next;
        }
    }
    return result;
}

#endif // #ifndef LISTLNK2_CPP
